\section{同 余 类 集}



\begin{frame}{等价关系与划分}

生活和数学中有各种关系。 例如同龄关系、师生关系、数的相等关系、整数的同余关系、向量组的线性等价关系、矩阵的等价等。
\pause
由上节定理 1 知道，同余关系满足传递性、对称性、自反性。 
高代中我们知道向量组的线性等价关系、矩阵的等价也满足这三个性质。
满足这三种性质的关系称为等价关系。
\pause
粗略地说，集合$S$上的等价关系就是从集合$S$出发用给定的法则等同$S$中的元素（我们想忽略被等同的元素的差异）。
这时可以得到新的集合。比如整数可以分成两类：偶数与奇数。

\pause
集合$S$上的\emph{等价关系} (equivalence relation) 是$S$中某些元素的关系，通常记为$a\sim b$, 称为$a$与$b$的一个\emph{等价}。等价关系要求：
\begin{enumerate}
    \item 自反性：对任意的$a\in S$, $a\sim a$;
  \item 对称性：若$a\sim b$, 则$b\sim a$;
  \item 传递性：若$a\sim b$, $b\sim c$, 则$a\sim c$.
\end{enumerate}
\pause
形式上讲，$S$上的\emph{关系}指$S\times S$的一个子集$R$. 
此时，等价关系满足的条件可描述为：
\begin{enumerate}
  \item 自反性：对任意的$a\in S$, $(a,a)\in R$;
  \item 对称性：若$(a,b)\in R$, 则$(b,a)\in R$;
  \item 传递性：若$(a,b), (b,c)\in R$, 则$(a,c)\in R$.
\end{enumerate}
\end{frame}

\begin{frame}



集合上的等价关系与集合的划分在逻辑上是相等的概念。
集合$S$的\emph{划分} (partition) 指一些$S$的互不相交的非空子集，
满足这些子集的并是$S$. 我们也把满足这些条件的$S$的子集构成的集合来表示这样的一个划分。
比如$\{1,2,3,4,5\}$的一个划分：$\{\{1,3\}, \{2,5\}, \{4\}\}$.

~

\pause
设集合$S$上有等价关系$\sim$. 对$a\in S$, 记$\bar{a} =\{b\in S\mid a\sim b\}$, 
这个称为$a$的\emph{等价类} (equivalence class)。
容易发现$\bar{a}\cap \bar{b}\neq \emptyset$当且仅当$\bar{a}=\bar{b}$. 
这样所有的等价类的集合$\{\bar{a} \mid a\in S\}$就给出了$S$的一个划分。
反过来，设$S$上有个划分$\bar{S}=\{S_i\mid i\in I\}$, 且设$i\neq j$时$S_i\neq S_j$. 
那么有$i\neq j$时$S_i\cap S_j=\emptyset$, 且$S=\sqcup_{i\in I}S_i$. 
此时，定义$S$上的关系：$a\sim b$当且仅当存在某个$S_i$使得$a,b\in S_i$. 
容易验证这个是等价关系，且所有的等价类恰为这些$S_i$.

~

\pause
给定集合$S$上的等价关系或划分$\bar{S}$，我们有典范的满射：$S\rightarrow \bar{S}, x\mapsto \bar{x}$, 其中$\bar{x}$表示$x$所在的等价类。若$S$有良好的结构（比如群、环、拓扑空间等等），对于特定的等价关系或划分，$\bar{S}$有诱导的同类结构，这种结构称为\emph{商}（相应地有商群、商环、商拓扑空间等等）。
\end{frame}

\begin{frame}{同 余 类 集}





%满足这三种性质的关系称为\emph{等价关系} (equivalent relation), 有此关系的两个对象称为\emph{相互等价}。
%例如，同余关系、同龄关系、同性别关系、同国籍关系、同奇偶关系均是等价关系。
%
%\pause
%可以按等价关系将对象集 $S$ 划分为\emph{等价类}。 
%\pause
%例如按同龄关系将学生划分为同龄类，有 18 岁类、19岁类等。 按同性别关系将学生分为男、女生两类。
%
%\pause
%以 $\bar{a}$ 记“与 $a$ 等价的元素集” (称为 $a$ 所代表的等价类， $a$ 称为该类的\emph{代表元} (representative)). 
%\pause
%按照一个等价关系将对象集 $S$ 分类的结果， 有如下特点：
%
%\pause
% (1) 每个等价类 $\bar{a}$ 是非空集合 (因为等价关系的自反性).
%
% \pause
% (2) 若 $a$ 与 $a^{\prime}$ 等价， 则 $\bar{a}=\overline{a^{\prime}}$ (因为等价关系的传递性和对称性， $x$ 与 $a$ 等价当且仅当 $x$ 与 $a^{\prime}$ 等价); 换言之， 等价类 $\bar{a}$ 中任一元素 $a^{\prime}$ 皆可做本类代表元。
%
% \pause
%(3) 若 $a$ 与 $a^{\prime}$ 不等价， 则 $\bar{a} \cap \overline{a^{\prime}}=\varnothing$ 为空集 (因若存在 $x \in \bar{a} \cap \overline{a^{\prime}}$, 则 $a$ 和 $a^{\prime}$均与 $x$ 等价， 故 $a$ 与 $a^{\prime}$ 等价， 矛盾); 
%\pause
%故对象集 $S$ 是所有等价类的无交并。


现在， 设 $m$ 为固定的非零整数， 按照模 $m$ 同余关系， 将整数集 $\mathbb{Z}$ 分类：相互同余者分在同一类， 称为\emph{模 $m$ 的一个同余类} (congruence class modulo $m$).
\pause
同余于 $a$ 的同余类 (即 $a$ 所代表的同余类)记为
\[
  \bar{a}=a+m \mathbb{Z}=\{a+m k \mid k \in \mathbb{Z}\}.
\]
\pause
于是整数集 $\mathbb{Z}$ 被划分为 $m$ 个同余类的无交之并：
\[
\mathbb{Z}=(m \mathbb{Z}) \cup(1+m \mathbb{Z}) \cup \cdots \cup(m-1+m \mathbb{Z})
\]

例如， 当 $m=7$ 时， 整数集 $\mathbb{Z}$ 被划分为 $7$ 个同余类：

\pause
同余于 $0$ 的类为 $\{\cdots,-14,-7,0,7,14,\cdots\}=7 \mathbb{Z}=\overline{0}$;

\pause
同余于 $1$ 的类为 $\{\cdots,-13,-6,1,8,15,\cdots\}=1+7 \mathbb{Z}=\overline{1}$;


\pause
同余于 $2$ 的类为 $\{\cdots,-12,-5,2,9,16,\cdots\}=2+7 \mathbb{Z}=\overline{2}$;

\quad $\vdots$

同余于 $6$ 的类为 $\{\cdots,-8,-1, 6,13,20,\cdots\}=6+7 \mathbb{Z}=\overline{6}$.

\pause
通俗地说，这就是把所有的星期日合记为 $7 \mathbb{Z}=\overline{0}$ （可称为 “星期日”或 “星期零”), 把所有的星期一合记为 $1+7 \mathbb{Z}=\overline{1}$ (可称为“星期一”), 等。
\end{frame}

\begin{frame}

\pause
现在， 我们有了一个崭新的集合， 即整数模 $m$ 的同余类的集合：
\[
  \mathbb{Z} / m \mathbb{Z}=\{\overline{0}, \overline{1}, \overline{2}, \cdots, \overline{m-1}\}.
\]
\pause
此集合共 $m$ 个元素，每一个元素是“一个同余类”. 例如， $m=7$ 时，
\[
\mathbb{Z} / 7 \mathbb{Z}=\{\overline{0}, \overline{1}, \overline{2}, \cdots, \overline{6}\}
\]
\pause
$\overline{0}, \overline{1}, \overline{2}, \cdots, \overline{6}$ 分别是 “星期零” “星期一”...“星期六”. 这是 $7$ 个 “星期数”.

~

\pause
对 $\mathbb{Z} / m \mathbb{Z}$ 的 $m$ 个同余类 $\overline{0}, \overline{1}, \overline{2}, \cdots, \overline{m-1}$, 
\pause
它们的代表元通常分别取为
\[
  0,1,2, \cdots, m-1,
\]
\pause
这称为模 $m$ 的\emph{最小非负(完全)代表元系} (或 \emph{(完全)剩余系}， complete residue system). 
\pause
有时也取代表元为 
\[
  -\frac{m-1}{2},\cdots,-2, -1, 0, 1, 2, \cdots, \frac{m-1}{2} \quad (\text{当 $m$ 为奇数}), 
\]
或 
\[
  -(\frac{m}{2}-1), \cdots, -1, 0, 1, \cdots, \frac{m}{2}-1, \frac{m}{2}\quad (\text{当 $m$ 为偶数}),
\]
称为\emph{绝对 (值)最小代表元系} (或\emph{剩余系}) (在所有的(完全)代表元系中，这组代表元的绝对值最大者最小)。
\end{frame}

\begin{frame}
现在我们试图在同余类集 $\mathbb{Z} / m \mathbb{Z}=\{\overline{0}, \overline{1}, \overline{2}, \cdots, \overline{m-1}\}$ 中引入运算。 
%\pause
%设想一下， 若问：星期三加星期五是多少? 大约都会回答：等于星期八---噢， 等于星期一。 那星期三乘星期五呢? 会回答： 等于星期十五---噢， 是星期一。 
%\pause
%因此引入如下定义是自然的。

\begin{definition}%定义1
记 $\mathbb{Z} / m \mathbb{Z}=\{\overline{0}, \overline{1}, \overline{2}, \cdots, \overline{m-1}\}$ 为整数模 $m$ 的同余类集， 
\pause
定义同余类 $\bar{a}$ 和 $\bar{b}$ 的加法和乘法如下：
\[
  \bar{a}+\bar{b}=\overline{a+b}, \quad \bar{a} \cdot \bar{b}=\overline{a b}
\]
\pause
(也可写为 $(a+m \mathbb{Z})+(b+m \mathbb{Z})=a+b+m \mathbb{Z},(a+m \mathbb{Z}) \cdot(b+m \mathbb{Z})=a b+m \mathbb{Z})$. $\bar{a} \cdot \bar{b}$ 也记为 $\bar{a} \bar{b})$.
\end{definition}

\pause
也就是说， 两个同余类 $\bar{a}$ 与 $\bar{b}$ 相加时， 是由它们的代表 $a, b$ 相加， 代表之和 $a+b$ 所在的同余类就是两个同余类之和。
\pause
对乘法也类似。 
\pause
我们需要验证此定义的合理性， 即代表的不同选取不影响结果。
\pause
事实上， 若在 $\bar{a}$ 中选取不同的代表元 $a, a^{\prime}$, 在 $\bar{b}$ 中选取不同的代表元 $b, b^{\prime}$, 则 $a^{\prime}=a+m s, b^{\prime}=b+m t$ ($s, t \in \mathbb{Z}$), 于是
\[
  \begin{aligned}
    a^{\prime}+b^{\prime}&= a+b+m(s+t),  & \text{故} &&
    \overline{a^{\prime}+b^{\prime}}&= \overline{a+b}; \\
a^{\prime} b^{\prime}&= a b+m(b s+a t+m s t), & \text{故} &&
\overline{a^{\prime} b^{\prime}}&= \overline{a b}.
\end{aligned}
\]
\pause
现在， 我们有了一个集合 $\mathbb{Z} / m \mathbb{Z}$ (共 $m$ 个元素， 每个元素是一个同余类),其中的元素有加法和乘法运算， 而且性质与整数运算类似， 因此我们称 $\mathbb{Z} / m \mathbb{Z}$为环。 
\end{frame}

\begin{frame}{环}


详言之， 环的定义如下。

\begin{definition}%定义2
  [环，ring]
  设 $R$ 是一个集合，其中的元素之间有两种二元运算，分别称为加法和乘法 (即任意的 $a, b \in R$ 对应着唯一的 $a+b \in R$, 和唯一的 $a b \in R$ ), 且满足如下条件 (对任意 $\alpha, \beta, \gamma \in R$ ), 则 $R$ 称为\emph{环} (ring) 或\emph{含幺环}：

  \pause
  (A) $R$ 中加法满足 ($R$带上加法构成Abel群)：

A1 (加法封闭性) $\alpha+\beta \in R$; (我们说加法是二元运算时已经自动要求了这点）

A2 (加法结合律) $(\alpha+\beta)+\gamma=\alpha+(\beta+\gamma)$;

A3 (存在加法单位元 (零元)) $R$ 中有一个元素 (记为 $0$), 使 $0+\alpha=\alpha$ 对任意 $\alpha \in R$ 成立;

A4 (存在加法逆元 (负元) ) 对任意 $\alpha \in R$, 存在 $\alpha^{\prime} \in R$, 使 $\alpha+\alpha^{\prime}=0$ (此 $\alpha^{\prime}$ 称为 $\alpha$ 的\emph{负元}， 记为 $-\alpha)$;

A5 (加法交换律) $\alpha+\beta=\beta+\alpha$.

\pause
(M) $R$ 中乘法满足：

M1 (乘法封闭性) $\alpha \beta \in R$; (我们说乘法是二元运算时已经自动要求了这点）

M2 (乘法结合律) $(\alpha \beta) \gamma=\alpha(\beta \gamma)$;

M3 (存在乘法单位元(幺元)) $R$ 中有元素 (记为 $e$ 或 $1$), 使 $e \alpha=a e=\alpha$ 对任意 $\alpha \in R$ 成立 (此元素 $e$ 称为 $R$ 的\emph{幺元}， 或\emph{乘法单位元});

\pause
(D) $R$ 中乘法对加法满足分配律： $\alpha(\beta+\gamma)=\alpha \beta+\alpha \gamma, (\beta+\gamma) \alpha=\beta \alpha+\gamma \alpha$.

\pause
若环 $R$ 中乘法还满足交换律(C)， 即 $\alpha \beta=\beta \alpha$ (对任意 $\alpha, \beta \in R$ ), 则称 $R$ 为\emph{交换环}。
\end{definition}
\end{frame}

\begin{frame}
  故一个（非零环\footnote{零环指单个零构成的环。含幺环为零环相当于$1=0$. 通常我们忽略这样平凡的环。}的）含幺环 $R$ 中， 最少有两个元素： 零元 (加法单位元) 和幺元 (乘法单位元), 常记为 $0$ 和 $1$. 
(容易验证这两个单位元都是惟一的。）
\pause
因为环中元素存在负元 (A4), 故环中可进行减法， 即规定
\[
  \alpha-\beta=\alpha+(-\beta).
\]
\pause
因此， 环中可进行加、减、乘运算， 环对加减乘封闭。

\pause
最著名的环是整数环 $\mathbb{Z}$, 即整数集合对普通的加法和乘法是一个环（满足定义 2).

\pause
也容易验证， 模 $m$ 的同余类集 $\mathbb{Z} / m \mathbb{Z}=R$ 满足定义 2, 是环。
\pause
事实上， 对 A3, 取 $0=\overline{0}$ 即为零元。 而对 A4, 若 $\alpha=\bar{a}$, 取 $\alpha^{\prime}=\bar{a}$ 则为其负元， 因为
\[
\alpha+\alpha^{\prime}=\bar{a}+\overline{-a}=\overline{a+(-a)}=\overline{0}=0
\]
对 M3, 取 $e=1=\overline{1}$ 即为幺元。 故 $\mathbb{Z} / m \mathbb{Z}$ 是环， 称为\emph{模 $m$ 的同余类环} (或\emph{模 $m$ 的商环}).

\pause
我们所熟悉的许多代数系统是环。 例如有理数系数的多项式集合 $\mathbb{Q}[X]$ 是 (含幺交换)环， 称为\emph{多项式(形式)环}。 
\pause
高斯整数集 $\mathbb{Z}[\mathrm{i}]=\{m+n \mathrm{i} \mid m, n \in \mathbb{Z}\}$ 也是含幺交换环 (其中 $i=\sqrt{-1}$). 
\pause
再如，有理数集 $\mathbb{Q}$ 、实数集 $\mathbb{R}$ 、复数集 $\mathbb{C}$ 都是环。
再如，
若$F$为数域（或一般的含幺交换环），$F$上的$n$阶矩阵构成的集合$M_n(F)$在矩阵的加法和乘法下构成含幺环 (通常非交换，除非$n=1$)。
\end{frame}

\begin{frame}{域}
  \begin{definition}%定义3
    [域， field]
    设 $F$ 为含幺交换环 (加法单位元记为 $0$, 乘法单位元记为 $1$), 且 $F$ 中任一非零元 $\alpha$ 均可逆， 即存在 $\alpha^{\prime} \in F$ 使 $\alpha^{\prime} \alpha=1$ (此 $\alpha^{\prime}$ 称为 $\alpha$ 的\emph{逆 (元)}, 记为 $\alpha^{-1}$ ), 则称 $F$ 为\emph{域}。
\end{definition}

\pause
域 $F$ 中可定义除法为 $a \div b=a b^{-1}$ (对 $a, b \in F, b \neq 0$). 
\pause
故域中可进行加减乘除运算，域对加减乘除封闭。

\pause
例如， 有理数集 $\QQ$ 为域， 称为\emph{有理数域}。 实数集 $\mathbb{R}$ 为域， 称为\emph{实数域}。 复数集 $\mathbb{C}$ 是域， 称为\emph{复数域}。 
\pause
高斯有理数集 $\mathbb{Q}(\mathrm{i})=\{a+b \mathrm{i} \mid a, b \in \mathbb{Q}\}$ 是域 (对复数的加法乘法). 
\pause
同样可知， $\mathbb{Q}(\sqrt{5})=\{a+b \sqrt{5} \mid a, b \in \mathbb{Q}\}$ 是域。 
\pause
再如， 域 $F$ 上的有理式集 $F(X)$ 也是域。

\pause
现在我们看
\[
\mathbb{Z} / 7 \mathbb{Z}=\{\overline{0}, \overline{1}, \cdots, \overline{6}\}
\]
已知是含幺交换环。 
\pause
其实 $\mathbb{Z} / 7 \mathbb{Z}$ 是一个域：任意非零元可逆。
\pause
事实上， $\overline{1}, \overline{2}$, $\overline{3}, \overline{4}, \overline{5}, \overline{6}$ 的逆分别为 $\overline{1}, \overline{4}, \overline{5}, \overline{2}, \overline{3}, \overline{6}$. 例如 $\overline{3} \cdot \overline{5}=\overline{15}=\overline{1}$.

\pause
次看 $\mathbb{Z} / 2 \mathbb{Z}=\{\overline{0}, \overline{1}\}, \overline{0}=2 \mathbb{Z}$ 就是偶数集， $\overline{1}=1+2 \mathbb{Z}$ 就是奇数集。 $\mathbb{Z} / 2 \mathbb{Z}$也是域。 
\pause
事实上， 其中非零元只有 $\overline{1}=1$ (幺元), 它的逆就是自身。 所以， $\mathbb{Z} / 2 \mathbb{Z}$ 中有四则运算： 加减乘除。 $(\mathbb{Z} / 2 \mathbb{Z}$ 称为\emph{二元域}， 在数字信息科技中特别重要。)
\end{frame}

\begin{frame}
再看 $\mathbb{Z} / 8 \mathbb{Z}=\{\overline{0}, \overline{1}, \cdots, \overline{7}\}$, 是含幺交换环， 但性质“不太好”. 
\pause
首先， 我们看到
\[
  \overline{4} \cdot \overline{6}=\overline{24}=\overline{0}, \quad \text { 而 } \quad \overline{4} \neq \overline{0}, \overline{6} \neq \overline{0}.
\]
\pause
在一个环 $R$ 中， 如果
\[
\alpha \beta=0 \text {~而~} \alpha \neq 0 \text {~且~} \beta \neq 0,
\]
则称 $\alpha$ 和 $\beta$ 为\emph{零因子} (divisor of zero).

\pause
没有零因子 (或者说，任意两个非零元素的乘积总非零) 的含幺交换环称为\emph{整环} (integral ring, 或 domain). 
\pause
我们熟悉的整数环 $\mathbb{Z}$ 、多项式环 $F[X]$ 都不含零因子，都是整环，是性质“好”的环。
\pause
但 $\mathbb{Z} / 8 \mathbb{Z}$中， $\overline{4} \cdot \overline{6}=\overline{0}$, 说明 $\overline{4}, \overline{6}$ 是零因子。 
\pause
而这又派生出 $\mathbb{Z} / 8 \mathbb{Z}$ 的另一个 “不好” 的性质： 非零元不一定有逆 (在 $\mathbb{Z} / 8 \mathbb{Z}$ 中). 
\pause
例如 $\overline{6}$ 没有逆; 否则， 若 $\overline{6}$ 有逆 $\overline{6}^{-1}$, 则在 $\overline{4} \cdot \overline{6}=\overline{0}$ 两边皆乘 $\overline{6}^{-1}$, 得到 $\overline{4}=\overline{0}$, 即 $8 \mid 4$, 矛盾。 
\pause
$\mathbb{Z} / 8 \mathbb{Z}$ 的这两点性质与 $\mathbb{Z} / 7 \mathbb{Z}$ 截然不同，原因在于 $8$ 是合数（有真因子)，而 $7$ 是素数。
\pause
实际上，含幺交换环中零因子必定不可逆 {\verify}。

\pause
再注意， $\mathbb{Z} / 8 \mathbb{Z}$ 中的可逆元集恰为
\[
U_{8}=\{\overline{1}, \overline{3}, \overline{5}, \overline{7}\},
\]
\pause
它们的逆元都是自身 $(\overline{3} \cdot \overline{3}=\overline{1}, \overline{5} \cdot \overline{5}=\overline{1}, \overline{7} \cdot \overline{7}=\overline{1})$, 而且对乘法封闭 $(\overline{3} \cdot \overline{5}=$ $\overline{7}, \overline{3} \cdot \overline{7}=\overline{5}, \overline{5} \cdot \overline{7}=\overline{3}$ ). 
\pause
因此， 称 $U_{8}$ 是 \emph{Klein (克莱因) 四元群} (Klein fourgroup).

\pause
最后看 $\mathbb{Z} / 10 \mathbb{Z}$, 可逆元为 $\overline{1}, \overline{3}, \overline{7}, \overline{9}$, 例如 $\overline{3}, \overline{7}$ 互为逆。
\end{frame}

\begin{frame}
  \begin{comment*}%评述
  同余式是 Gauss 划时代著作《算术研究》的开卷内容。 Gauss 天才地引入同余式概念， 后来有了惊人深广的发展应用 (商群、商系统、有限域环等系统， 完备化局部化). 按同余关系将整数分类， 每类作为一元构成新的集合 (常选一个代表), 再定义类之间的运算， 就创造出一个崭新的系统一同余类环，或商环。论数者赞这“商环之妙”曰：
  \begin{poem}
  物以类分自古然， 每类一席成商环。\\
亚当夏娃代男女， 千年月日归七天。
\end{poem}
\end{comment*}\end{frame}
\begin{frame}{小结}
  \begin{enumerate}
    \item 何为集合上的等价关系？何为集合的划分？二者如何在逻辑上等价？
    \item 何为环？何为交换环？何为域？何为整环？何为零因子？
    \item 模$m$的同余类构成的集合$\ZZ/m\ZZ$的环结构如何定义？
  \end{enumerate}
\end{frame}
